Animation is the process of simulating movement by displaying a series of successive images on a visual display screen. One common approach in computer animation is to create many static frames which contain various images overlaid on a background. Images which are to be depicted in motion have slightly different positions in each frame. The frames are shown sequentially according to an animation script at a sufficient speed that the images appear in motion across the visual display screen.
For successful animation sequences, images must replace one another rapidly enough to fool the eye into seeing continuous movement. An appropriate threshold rate is 14 frames per second (fps). Broadcast-quality animation typically ranges from 14 to 30 fps. Television sets run at a constant rate of 30 fps. Film animation displays at 24 fps. Animation of cartoons for film is played at 24 fps, with each frame being displayed twice in sequence.
Computer animation is a type of animation where the frame images are generated electronically. In computer animation, the animator defines an object according to a mathematical function or model. A computer program uses the mathematical function to derive various two dimensional images of the object which can be shown on the visual display screen.
Computer animation can be created in real-time, in which each frame is created as the viewer watches. The objects portrayed in real time animation are typically very simplistic so that the computer can quickly generate the images and transfer them to the visual display screen. Computers today typically animate objects in real-time at 4-14 fps, although a few very powerful computers can animate graphics at 30 fps.
Computer animation can also be created in simulated time where still frames are generated and then subsequently arranged in a real time presentation via other media formats, such as print, photography, film, or video. In this manner, the computer can spend minutes or even hours creating each still frame, but the display of the frames can be performed at any desired speed.
One problem encountered in computer animation is "aliasing." This problem arises because the object being portrayed on screen is described by a continuous and non-bandlimited mathematical function. The display screen, however, is composed of a matrix of discrete pixels (short for "picture elements"). To represent the continuous object, referred to as the "source object", in terms of discrete pixels, the computer calculates numerous samples of the object based on the mathematical function to derive pixel datum. The pixel datum is used to illuminate the screen pixels. Some information contained in the source object is lost due to this sampling technique.
According to the Nyquist limit, only those frequencies that are lower than one-half of the sampling rate can be accurately represented. An attempt to display frequencies greater than the Nyquist limit can produce aliasing artifacts. Common types of aliasing artifacts include "jaggies" on the edges of objects, jagged highlights, strobing and other forms of temporal aliasing, and patterns in texture. Aliasing artifacts are unacceptable in computer animation, particularly in animation attempting to yield realistic images.
Two prior art solutions to reduce aliasing artifacts are "supersampling" and "adaptive sampling". Supersampling involves using more than one regularly spaced sample per pixel. It reduces aliasing by raising the Nyquist limit, but does not eliminate aliasing. Adaptive sampling adds additional rays near the object edges. "Rays" are generated according to a complex image synthesizing technique known as "ray tracing" which calculates the attributes of each pixel in relation to the viewer, to other objects in the image, and to the light source for the image. The attributes are computed by tracing single rays of light backward to see the way the rays were affected as they traveled from the defined source of light illuminating the object, to the object, and to the viewer's eye. Adaptive sampling reduces aliasing at the edges, but often requires a large number of rays.
Another prior art solution, known as "stochastic sampling", effectively eliminates aliasing. In stochastic sampling, an image is sampled at random irregular spaced locations rather than uniform spaced locations. Frequencies above the Nyquist limit are still inadequately sampled, but appear as noise rather than coherent aliasing artifacts. Accordingly, stochastic sampling replaces the highly objectionable aliasing artifacts with tolerable noise. A more detailed discussion of stochastic sampling can be found in the following documents, which are hereby incorporated by reference:
1. Progress in Computer Graphics: Volume 1, edited by Zobrist and Sabharwal, Chapter 1 entitled "Stochastic Sampling: Theory and Application" by Mark A. Z. Dippe and Erling Henry Wold, Ablex Publishing Corp., pgs. 1-55; and PA1 2. Stochastic Sampling in Computer Graphics, Robert L. Cook, ACM Transactions on Graphics, Vol. 5, No. 1, pgs. 51-72 (January 1986).
To reduce noise in stochastic sampling, more sample points must be taken. Many samples are required to produce images which appear free of noise, especially for procedural textures or the shadowing effects of area light sources. Unfortunately, additional samples are costly. The signal-to-noise ratio is proportional to the square root of the number of samples taken. Accordingly, a significant number of samples must be taken to gain even modest improvement in the signal-to-noise ratio.
Accordingly, there remains a need for techniques to reduce noise introduced by stochastic sampling.